package q169_majorityElement;

public class Solution {
    public static void main(String[] args) {

    }


    /***
     * 众数算法，如果我们把每一个众数看为1，其他看为-1，那么一次循环下来，一定是一个正数，因为在数组里面众数的数量达到一半以上
     * 所以，我们只需要进行判断：
     * 如果一开始count为0，我们就把众数设置为第一个数，然后在与后面的数比较，如果相等，就count++，否则count--
     * 那么非众数必定在某一个归零，这个时候又要寻找新的众数为candidate，到达数组最后的时候，一定是众数留在了candidate中
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count++;
                continue;
            }
            if (candidate == nums[i]){
                count++;
            }else {
                count--;
            }
        }

        return candidate;
    }
}
